package leetcode.editor.cn;

class TrimABinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new TrimABinarySearchTree().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 递归一
         * @param root
         * @param low
         * @param high
         * @return
         */
        public TreeNode trimBST(TreeNode root, int low, int high) {
            if (root == null) {
                return null;
            }

            if (root.val < low) {   // 此时该节点值小于最小边界，返回有节点，因为左边的节点更小
                return trimBST(root.right, low, high);
            }

            if (root.val > high) {
                return trimBST(root.left, low, high);
            }

            root.left = trimBST(root.left, low, high);  // 用父节点左边刚删除的节点（此时空缺），来接住返回的右节点
            root.right = trimBST(root.right, low, high); // 同理

            return root;
        }


        // 使用450的思路，但是是后序，在范围中才进行删除
        // 没有使用BST的性，而是相当于普通树进行删除处理
        /*public TreeNode trimBST(TreeNode root, int low, int high) {
            if (root == null) return null;

            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);

            // 也是使用450删除的思路，只不过后序遍历来删除
            if (root.val >= low && root.val <= high) {
                return root;
            } else {
                if (root.right == null) return root.left;

                TreeNode tmp = root.right;
                while (tmp.left != null) {
                    tmp = tmp.left;
                }

                tmp.left = root.left;
                return root.right;
            }
        }*/

        /**
         * 迭代法
         *
         * @param root
         * @param low
         * @param high
         * @return
         */
        /*public TreeNode trimBST(TreeNode root, int low, int high) {
            if (root == null) {
                return null;
            }

            // 处理头结点，让root移动到[low,high]的区间中
            while (root != null && (root.val < low || root.val > high)) {    // 迭代root到区间外时停止迭代
                if (root.val < low) {   // 小于则往右递归
                    root = root.right;
                } else {    // 大于则往左递归
                    root = root.left;
                }
            }

            TreeNode cur = root;
            // 此时root已经在[low,high]的区间，处理左孩子小于low的情况
            while (cur != null) {
                while (cur.left != null && cur.left.val < low) {
                    cur.left = cur.left.right;
                }
                cur = cur.left;
            }

            cur = root;
            // 此时root已经在[low,high]的区间，处理右孩子大于low的情况
            while (cur != null) {
                while (cur.right != null && cur.right.val > high) {
                    cur.right = cur.right.left;
                }
                cur = cur.right;
            }

            return root;
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
